<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>Iterators</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>Iterators</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "iterators.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "overview.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: iterators</TD>
<TD Align=right VAlign=top><b>Component type</b>: overview</TD>
</TR>
</Table>

<h3>Summary</h3>
Iterators are a generalization of pointers: they are
objects that point to other objects.  As the name suggests, iterators
are often used to iterate over a range of objects: if an iterator
points to one element in a range, then it is possible to increment
it so that it points to the next element.
<P>
Iterators are central to generic programming because they are an
interface between containers and algorithms: algorithms typically
take iterators as arguments, so a container need only provide a way to
access its elements using iterators.  This makes it possible to write
a generic algorithm that operates on many different kinds of
containers, even containers as different as a <A href="Vector.html">vector</A> and a
<A href="List.html">doubly linked list</A>.
<P>
The STL defines several different concepts related to iterators,
several predefined iterators, and a collection of types and functions
for manipulating iterators.
<h3>Description</h3>
Iterators are in fact not a single concept, but six concepts that
form a hierarchy: some of them define only a very restricted set of
operations, while others define additional functionality.  The 
five concepts that are actually used by algorithms are
<A href="InputIterator.html">Input Iterator</A>, <A href="OutputIterator.html">Output Iterator</A>, <A href="ForwardIterator.html">Forward Iterator</A>,
<A href="BidirectionalIterator.html">Bidirectional Iterator</A>, and <A href="RandomAccessIterator.html">Random Access Iterator</A>.  A sixth
concept, <A href="trivial.html">Trivial Iterator</A>, is introduced only to clarify the 
definitions of the other iterator concepts.
<P>
The most restricted sorts of iterators are <A href="InputIterator.html">Input Iterators</A> and
<A href="OutputIterator.html">Output Iterators</A>, both of which permit &quot;single pass&quot; algorithms
but do not necessarily support &quot;multi-pass&quot; algorithms.  
<A href="InputIterator.html">Input iterators</A> only guarantee read access: it is possible to
dereference an <A href="InputIterator.html">Input Iterator</A> to obtain the value it points to,
but not it is not necessarily possible to assign a new value through
an input iterator.  Similarly, <A href="OutputIterator.html">Output Iterators</A> only guarantee
write access: it is possible to assign a value through an 
<A href="OutputIterator.html">Output Iterator</A>, but not necessarily possible to refer to that value.
<P>
<A href="ForwardIterator.html">Forward Iterators</A> are a refinement of <A href="InputIterator.html">Input Iterators</A> and
<A href="OutputIterator.html">Output Iterators</A>: they support the <A href="InputIterator.html">Input Iterator</A> and
<A href="OutputIterator.html">Output Iterator</A> operations and also provide additional
functionality.  In particular, it is possible to use &quot;multi-pass&quot;
algorithms with <A href="ForwardIterator.html">Forward Iterators</A>.  A <A href="ForwardIterator.html">Forward Iterator</A> may be
<i>constant</i>, in which case it is possible to access the object it
points to but not to to assign a new value through it, or <i>mutable</i>,
in which case it is possible to do both.
<P>
<A href="BidirectionalIterator.html">Bidirectional Iterators</A>, like <A href="ForwardIterator.html">Forward Iterators</A>, allow
multi-pass algorithms.  As the name suggests, they are different in
that they support motion in both directions: a 
<A href="BidirectionalIterator.html">Bidirectional Iterator</A> may be incremented to obtain the next
element or decremented to obtain the previous element.  A 
<A href="ForwardIterator.html">Forward Iterator</A>, by contrast, is only required to support forward
motion.  An iterator used to traverse a singly linked list, for
example, would be a <A href="ForwardIterator.html">Forward Iterator</A>, while an iterator used to
traverse a doubly linked list would be a <A href="BidirectionalIterator.html">Bidirectional Iterator</A>.
<P>
Finally, <A href="RandomAccessIterator.html">Random Access Iterators</A> allow the operations of
pointer arithmetic: addition of arbitrary offsets, subscripting,
subtraction of one iterator from another to find a distance, and
so on.
<P>
Most algorithms are expressed not in terms of a single iterator but in
terms of a <i>range</i> of iterators <A href="#1">[1]</A>; the notation <tt>[first,
last)</tt> refers to all of the iterators from <tt>first</tt> up to, but <b>not
including</b>, <tt>last</tt>. <A href="#2">[2]</A> Note that a range may be empty, <i>i.e.</i>
<tt>first</tt> and <tt>last</tt> may be the same iterator.  Note also that if there
are <tt>n</tt> iterators in a range, then the notation <tt>[first, last)</tt>
represents <tt>n+1</tt> positions.  This is crucial: algorithms that
operate on <tt>n</tt> things frequently require
<tt>n+1</tt> positions.  Linear search, for example (<tt><A href="find.html">find</A></tt>) must be able
to return some value to indicate that the search was unsuccessful.
<P>
Sometimes it is important to be able to infer some properties of an
iterator: the type of object that is returned when it is dereferenced,
for example.  There are two different mechanisms to support
this sort of inferrence: an older mechanism called
<A href="iterator_tags.html">Iterator Tags</A>, and a newer mechanism called <tt><A href="iterator_traits.html">iterator_traits</A></tt>
<A href="#3">[3]</A>.
<h3>Concepts</h3>
<UL>
<LI>
 <A href="trivial.html">Trivial Iterator</A>
<LI>
 <A href="InputIterator.html">Input Iterator</A>
<LI>
 <A href="OutputIterator.html">Output Iterator</A>
<LI>
 <A href="ForwardIterator.html">Forward Iterator</A>
<LI>
 <A href="BidirectionalIterator.html">Bidirectional Iterator</A>
<LI>
 <A href="RandomAccessIterator.html">Random Access Iterator</A>
</UL>
<h3>Types</h3>
<UL>
<LI>
<tt><A href="istream_iterator.html">istream_iterator</A></tt>
<LI>
<tt><A href="ostream_iterator.html">ostream_iterator</A></tt>
</UL>
<UL>
<LI>
<tt><A href="ReverseIterator.html">reverse_iterator</A></tt>
<LI>
<tt><A href="ReverseBidirectionalIterator.html">reverse_bidirectional_iterator</A></tt>
<LI>
<tt><A href="insert_iterator.html">insert_iterator</A></tt>
<LI>
<tt><A href="front_insert_iterator.html">front_insert_iterator</A></tt>
<LI>
<tt><A href="back_insert_iterator.html">back_insert_iterator</A></tt>
</UL>
<UL>
<LI>
<tt><A href="iterator_traits.html">iterator_traits</A></tt>
</UL>
<UL>
<LI>
<tt><A href="input_iterator_tag.html">input_iterator_tag</A></tt>
<LI>
<tt><A href="output_iterator_tag.html">output_iterator_tag</A></tt>
<LI>
<tt><A href="forward_iterator_tag.html">forward_iterator_tag</A></tt>
<LI>
<tt><A href="bidirectional_iterator_tag.html">bidirectional_iterator_tag</A></tt>
<LI>
<tt><A href="random_access_iterator_tag.html">random_access_iterator_tag</A></tt>
</UL>
<UL>
<LI>
<tt><A href="input_iterator.html">input_iterator</A></tt>
<LI>
<tt><A href="output_iterator.html">output_iterator</A></tt>
<LI>
<tt><A href="forward_iterator.html">forward_iterator</A></tt>
<LI>
<tt><A href="bidirectional_iterator.html">bidirectional_iterator</A></tt>
<LI>
<tt><A href="random_access_iterator.html">random_access_iterator</A></tt>
</UL>
<h3>Functions</h3>
<UL>
<LI>
<tt><A href="distance_type.html">distance_type</A></tt>
<LI>
<tt><A href="value_type.html">value_type</A></tt>
<LI>
<tt><A href="iterator_category.html">iterator_category</A></tt>
</UL>
<UL>
<LI>
<tt><A href="distance.html">distance</A></tt>
<LI>
<tt><A href="advance.html">advance</A></tt>
</UL>
<UL>
<LI>
<tt><A href="insert_iterator.html">inserter</A></tt>
<LI>
<tt><A href="front_insert_iterator.html">front_inserter</A></tt>
<LI>
<tt><A href="back_insert_iterator.html">back_inserter</A></tt>
</UL>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Ranges are not a well-defined concept for <A href="trivial.html">Trivial Iterators</A>,
because a <A href="trivial.html">Trivial Iterator</A> cannot be incremented: there is no such  
thing as a next element.  They are also not a well-defined concept
for <A href="OutputIterator.html">Output Iterators</A>, because it is impossible to compare two 
<A href="OutputIterator.html">Output Iterators</A> for equality.  Equality is crucial to the
definition of a range, because only by comparing an iterator for
equality with the last element is it possible to step through a range.
<P><A name="2">[2]</A>
Sometimes the notation <tt>[first, last)</tt> refers to the iterators
<tt>first</tt>, <tt>first+1</tt>, ..., <tt>last-1</tt> and sometimes it refers to the
objects pointed to by those iterators: <tt>*first</tt>, <tt>*(first+1)</tt>, ...,
<tt>*(last-1)</tt>.  In most cases it will be obvious from context which of
these is meant; where the distinction is important, the notation will
be qualified explicitly as &quot;range of iterators&quot; or &quot;range of objects&quot;.
<P><A name="3">[3]</A>
The <tt><A href="iterator_traits.html">iterator_traits</A></tt> class relies on a C++ feature known as
<i>partial specialization</i>.  Many of today's compilers don't implement
the complete standard; in particular, many compilers do not support
partial specialization.  If your compiler does not support partial
specialization, then you will not be able to use
<tt><A href="iterator_traits.html">iterator_traits</A></tt>, and you will instead have to continue using the
functions <tt><A href="iterator_category.html">iterator_category</A></tt>, <tt><A href="distance_type.html">distance_type</A></tt>, and
<tt><A href="value_type.html">value_type</A></tt>.
<h3>See also</h3>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
